package com.hackerank.arrays;

import java.util.HashMap;
import java.util.Map;

/***
 * Sparse Arrays    零落的数组
 * https://www.hackerrank.com/challenges/sparse-arrays/problem
 *
 * 题目大意：
 *  1、输入数字n，接下来输入n行字符串，组成strings 数组
 *  2、输入数字q，接下来输入q行字符串，组成queries 数组
 *  3、在strings 数组中查询 queries数组中的每个字符串（完全匹配）
 *  4、输出 int类型数组，int[q],表示queries数组中每个字符串在strings数组中出现的次数
 *  5、如输入：
 * 4
 * aba
 * baba
 * aba
 * xzxb
 * 3
 * aba
 * xzxb
 * ab
 * 输出：
 * 2
 * 1
 * 0
 *
 *  解题思路：
 *  方法一：
 *  1、双重for循环查询，时间复杂度O(nq)
 *  方法二：
 *  1、先进行strings的 Map Hash，而后对queries中的值进行查询输出，时间复杂度O(n+q)
 *
 * */
public class SparseArrays {
    static int[] matchingStrings(String[] strings, String[] queries) {
        int[] result = new int[queries.length];
        Map<String,Integer> counter = new HashMap();
        for(String string : strings){
            Integer count = counter.get(string);
            if(count == null)
                count = 1;
            else
                count ++;
            counter.put(string,count);
        }
        for(int i=0;i<queries.length;i++){
            String query = queries[i];
            Integer count = counter.get(query);
            if(count == null)
                count = 0;
            result[i] = count;
        }
        return result;
    }
}
